/**
 * @file streamsummarybucket.cpp
 * @brief Implementation of Stream-Summary datastructure using map of buckets. See <a target=blank href=http://libra.msra.cn/Publication/1797081/efficient-computation-of-frequent-and-top-k-elements-in-data-streams>Metwally et al.: Efficient Computation of Frequent and Top-k Elements in Data Streams</a>
 * @author Andreas Bok Andersen
 * */
#include <boost/range/adaptor/map.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/assign.hpp>

#define STREAMSUMMARYBUCKET

#include "bucket2.h"
typedef pair<int, Bucket2> INT_BUCKET_PAIR;
typedef pair<size_t, Bucket2*> INT_ENTRY_BUCKET_REF_PAIR;
typedef unordered_map<size_t, Bucket2*> ENTRY_BUCKET2_REF_MAP;
typedef unordered_map<int, Bucket2> INT_BUCKET2_MAP;

class StreamSummaryBucket: public Summary::Summary {
private:
	ENTRY_BUCKET2_REF_MAP entries;
	INT_BUCKET2_MAP buckets;

	Bucket2* min_bucket;
	void add_item(int i, int j, float w);
	void increase(int i, int j, float w);
	void replace_min(int i, int j, float w);

public:
	StreamSummaryBucket(int k) :
			Summary::Summary(k) {
		this->min_bucket = NULL;
	}
	/**
	 * Inserts element into summary.
	 */
	void insert(int i, int j, float w) {
		//printf("\n(%d,%d,%.3f)\n", i, j, w);
		if (this->entries.find(hash_value(i, j)) != entries.end()) {
			//cerr << "INCREASE" << endl;
			this->increase(i, j, w);
		} else if (this->entries.size() < this->k) {
			//cerr << "ADD" << endl;
			this->add_item(i, j, w);
		} else {
			//cerr << "REPLACE" << endl;
			replace_min(i, j, w);
		}
	}

	ENTRY_VEC get_summary() ;
	void get_summary(Entry entries[]);
	void get_summary(ENTRY_VEC *entries);

	/**
	 * @return String representation of summary
	 */
	string to_string() {
		stringstream ss;
		Bucket2 b = *min_bucket;
		ss << b.to_string() << " -> ";
		while (b.next) {
			b = *b.next;
			ss << b.to_string() << " -> ";
		}
		return ss.str();
	}
	Entry get_min_el();
	int summarysize() {
		return this->entries.size();
	}
};

/**
 * Adds element to summary
 */
void StreamSummaryBucket::add_item(int i, int j, float w) {
	/*
	 * get new key
	 * make new entry
	 * get pointer
	 * New bucket
	 * if min == NULL :
	 * 		insert mew bucket
	 * 		add entry to bucket
	 * 		add entry to entries
	 * 		set min bucket
	 * */

	int key = (int) ceil(w);
	Entry e(i, j, w, 0.0);
	Bucket2 * b;
	if (this->min_bucket == NULL) {
		Bucket2 vb(key, NULL, NULL);
		this->buckets.insert(
				INT_BUCKET_PAIR(key, vb));
		b = &this->buckets.find(key)->second;
		(*b).add(e);
		this->entries.insert(INT_ENTRY_BUCKET_REF_PAIR(e.hash, b));
		this->min_bucket = b;
	} else if (this->buckets.find(key) == this->buckets.end()) {
		/*
		 * find insertion point
		 * insert new bucket
		 * add element to bucket
		 * update next
		 * add entry -> bucket mapping
		 *
		 * */
		Bucket2 _bucket = *min_bucket;

		while (_bucket.next && (*_bucket.next).key < key) {
			_bucket = *_bucket.next;
		}
		this->buckets.insert(
				INT_BUCKET_PAIR(key,
						Bucket2(key,
								&this->buckets.find(_bucket.key)->second,
								NULL)));
		b = &this->buckets.find(key)->second;
		(*b).add(e);
		if (_bucket.next) {
			(*b).next = this->buckets.find(_bucket.key)->second.next;
			(*this->buckets.find(_bucket.key)->second.next).prev = b;
		}
		this->buckets.find(_bucket.key)->second.next = b;
		this->entries.insert(INT_ENTRY_BUCKET_REF_PAIR(e.hash, b));
	} else {
		/*
		 * insert entry into bucket
		 * add mapping
		 * */
		b = &this->buckets.find(key)->second;
		(*b).add(e);
		this->entries.insert(INT_ENTRY_BUCKET_REF_PAIR(e.hash, b));
	}
}

/**
 * Increases value of existing item in summary
 */
void StreamSummaryBucket::increase(int i, int j, float w) {
	/*
	 * get entry
	 * get curr_bucket
	 * get new key
	 * init Bucket2*
	 *
	 * if has new key:
	 * 		if (new key != curr_key :
	 * 			update entry mapping
	 * 			add entry to existing bucket
	 * 			remove from curr_bucket
	 *
	 * */
	//cerr << this->to_string() << endl;
	size_t e_hash = hash_value(i, j);
	Bucket2 * curr_bucket = this->entries.find(e_hash)->second;
	//cerr << "curr " << (*curr_bucket).to_string() << endl;
	Entry * e = &curr_bucket->elements->find(e_hash)->second;
	(*e).weight = w + (*e).weight;
	int _key = (int) ceil((*e).weight);
	Bucket2 * bucket;
	if (this->buckets.find(_key) != this->buckets.end()) {
		if ((*curr_bucket).key != _key) {
			this->entries.find(e_hash)->second =
					&this->buckets.find(_key)->second;
			this->buckets.find(_key)->second.add(*e);
			this->buckets.find((*curr_bucket).key)->second.remove(*e);

		}
		//cerr << this->to_string() << endl;
	} else {
		/*
		 * find insertion point
		 * insert new bucket
		 * add entry to bucket
		 * if tmp.next
		 * update tmp.next
		 * update entry mapping
		 * remove entry from curr_bucket
		 * */
		Bucket2 _bucket = *curr_bucket;
		while (_bucket.next && (_bucket).key < _key) {
			_bucket = *_bucket.next;
		}

		Bucket2 * prev_bucket = &this->buckets.find(_bucket.key)->second;
		//cerr << "found insertion point: " << _bucket.to_string() << endl;
		//prinf("prev is null %d\n", (prev_bucket == NULL));
		bucket = new Bucket2(_key, prev_bucket, NULL);
		this->buckets.insert(
				INT_BUCKET_PAIR(_key, *bucket));
		//bucket = &this->buckets.find(_key)->second;
		//cerr << this->to_string() << endl;
		(*bucket).add(*e);

		if (_bucket.next) {
			//prinf("%s", "_bucket.next\n");
			(*(*prev_bucket).next).prev = bucket;
			(*bucket).next = (*prev_bucket).next;
		}
		//cerr << this->to_string() << endl;
		(*prev_bucket).next = bucket;
		this->entries.find((*e).hash)->second = bucket;
		(*curr_bucket).remove(*e);
		//cerr << this->to_string() << endl;
	}

	/*
	 * if curr !has elements
	 * 		if curr == min
	 * 				min = min.next
	 * 				min.prev = NULL
	 * 		else :
	 * 			if (curr.next) :
	 * 				curr.next.prev = curr.prev
	 * 		curr.prev.next = curr.next
	 * erase curr
	 * */
	if (!(*curr_bucket).has_elements()) {
		//prinf("%s\n", "curr is empty");
		if (curr_bucket == this->min_bucket) {
			this->min_bucket = (*this->min_bucket).next;
			(*this->min_bucket).prev = NULL;
		} else {
			if ((*curr_bucket).next) {
				(*(*curr_bucket).next).prev = (*curr_bucket).prev;
			}
			(*(*curr_bucket).prev).next = (*curr_bucket).next;
		}
		this->buckets.erase((*curr_bucket).key);
	}

	//cerr << "end increase " << this->to_string() << endl;
}
;

/**
 * @return Returns element with minimum value
 */
Entry StreamSummaryBucket::get_min_el() {
	Bucket2 b = *this->min_bucket;
	INT_ENTRY_MAP::iterator it = b.elements->begin();
	Entry min_el = it->second;
	for (; it != b.elements->end(); it++) {
		if (it->second.weight < min_el.weight)
			min_el = it->second;
	}
	return min_el;
}

/**
 * Replaces minimum element with a new item.
 */
void StreamSummaryBucket::replace_min(int i, int j, float w) {
	/*
	 * get min el
	 * new entry
	 * new key
	 * if has new bucket:
	 * 		get ref to bucket
	 * 		add e to bucket
	 * 		get e.ref
	 * 		insert e.ref bucket
	 * 	else :
	 * 		find insertion point
	 * 		make new bucket
	 * 		get ref
	 * 		insert el
	 * 	if _bucket.next
	 * 		update prev/next
	 * 	get min_bucket
	 * 	remove min_el from min_bucket
	 *
	 * if curr !has elements
	 * 		if curr == min
	 * 				min = min.next
	 * 				min.prev = NULL
	 * 		else :
	 * 			if (curr.next) :
	 * 				curr.next.prev = curr.prev
	 * 		curr.prev.next = curr.next
	 * 		erase curr_bucket
	 * erase curr_min
	 * */
	Entry min = get_min_el();
	//cerr << "found min" << (min).to_string() << endl;
	Entry e(i, j, w + min.weight, min.weight);

	int key = (int) ceil(e.weight);
	//cerr << e->to_string() << endl;
	//printf("new key: %d\n", key);
	Bucket2 * bucket;
	if (this->buckets.find(key) != this->buckets.end()) {
		bucket = &this->buckets.find(key)->second;
		//cerr << "new key exists" << endl;
	} else {
		//cerr << "!new key exists" << endl;
		Bucket2 _bucket = *this->entries.find(min.hash)->second;
		while (_bucket.next && (*_bucket.next).key < key) {
			_bucket = *_bucket.next;
		}
		Bucket2 * prev_bucket = &this->buckets.find(_bucket.key)->second;
		this->buckets.insert(
				INT_BUCKET_PAIR(key, *new Bucket2(key, prev_bucket, NULL)));
		bucket = &this->buckets.find(key)->second;
		if ((*prev_bucket).next) {
			(*bucket).next = (*prev_bucket).next;
			(*(*bucket).next).prev = bucket;
		}
		prev_bucket->next = bucket;
	}

	//printf("%s\n", "Adding el to bucket");
	(*bucket).add(e);
	//printf("%s\n", "Adding el to entries");
	this->entries.insert(INT_ENTRY_BUCKET_REF_PAIR(e.hash, bucket));
	//printf("%s\n", "Added Entry->Bucket ref");
	Bucket2 * curr_bucket = this->entries.find(min.hash)->second;
	//printf("%s\n", "Found curr.bucket");
	curr_bucket->remove(min);
	//printf("%s\n", "Removed min from current");
	if (!(*curr_bucket).has_elements()) {
		//printf("%s curr is NULL: %d min is NULL: %d", "Curr is empty",(curr_bucket == NULL), (this->min_bucket == NULL));

		if (curr_bucket == this->min_bucket) {
			this->min_bucket = min_bucket->next;
			this->min_bucket->prev = NULL;
			//printf("%s\n", "Updated Min bucket");
		} else {
			if (curr_bucket->next) {
				(*(*curr_bucket).next).prev = curr_bucket->prev;
			}
			(*(*curr_bucket).prev).next = (*curr_bucket).next;
			//printf("%s\n", "Update prev/next for curr");
		}
		this->buckets.erase((*curr_bucket).key);
		//printf("%s\n", "Erased curr bucket");
	}

	this->entries.erase(min.hash);
	//printf("Erased min\n");
}

/**
 * Fill entries into vector of Entry. Argument is passed by reference
 * @param entries pointer to vector<Entry>
 */
void StreamSummaryBucket::get_summary(ENTRY_VEC *summary) {
	Bucket2 min = *this->min_bucket;
	boost::copy(*min.elements | boost::adaptors::map_values,
			std::back_inserter(*summary));
	while (min.next) {
		min = *min.next;
		boost::copy(*min.elements | boost::adaptors::map_values,
				std::back_inserter(*summary));
	}
}
/**
 * Fill entries into array of Entry. Argument is passed by reference
 * @param entries[] pointer to array of Entry
 */
void StreamSummaryBucket::get_summary(Entry summary[]) {
	Bucket2 min = *min_bucket;
	INT_ENTRY_MAP::iterator it;
	int i = 0;
	for (it = min.elements->begin(); it != min.elements->end(); it++) {
		summary[i] = it->second;
		i++;
	}
	while (min.next) {
		min = *min.next;
		for (it = min.elements->begin(); it != min.elements->end(); it++) {
			summary[i] = it->second;
			i++;
		}

	}
}

ENTRY_VEC StreamSummaryBucket::get_summary() {
	ENTRY_VEC summary;
	Bucket2 min = *min_bucket;
	boost::copy(*min.elements | boost::adaptors::map_values,
			std::back_inserter(summary));
	while (min.next) {
		min = *min.next;
		boost::copy(*min.elements | boost::adaptors::map_values,
				std::back_inserter(summary));
	}
	return summary;
}
